package leetcode.editor.cn;

import java.util.*;
import leetcode.editor.common.*;

public class ValidParentheses {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isValid(String s) {
            // 为奇数长度，肯定不合法
            if(s==null||s.length()%2==1){
                return false;
            }
            // 使用栈来解决，遇到左括号就入栈，遇到右括号就出栈，如果出栈的括号和入栈的括号不匹配，则返回false
            final Stack<Character> stack = new Stack<>();
            final char[] chars = s.toCharArray();

            for (char charStr : chars){
                if('('==charStr||'{'==charStr||'['==charStr){
                    stack.push(charStr);
                }

                if(')'==charStr||'}'==charStr||']'==charStr){
                    if(stack.isEmpty()){
                        return false;
                    }
                    final Character pop = stack.peek();
                    if(pop=='('&&charStr==')'){
                        stack.pop();
                        continue;
                    }
                    if(pop=='{'&&charStr=='}'){
                        stack.pop();
                        continue;
                    }
                    if(pop=='['&&charStr==']'){
                        stack.pop();
                        continue;
                    }

                    // 说明有不成对的括号，直接退出
                    return false;

                }

            }
            if(stack.isEmpty()){
                return true;
            }

            return false;

        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    
    public static void main(String[] args) {
        Solution solution = new ValidParentheses().new Solution();
        // put your test code here
        System.out.println(solution.isValid("([}}])"));
    }
}
